package com.yun.alg;

import java.util.Arrays;

/**
 * Created by lsy
 * on 2020/6/11 15:53.
 */
public class QuickSort {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] ary = {5, 4, 7, 88, 99, 33, 11, 33};
        quickSort.quickSort(ary);
        System.out.println(Arrays.toString(ary));
    }

    public void quickSort(int[] ary) {
        quickSortBaseFirst(ary, 0, ary.length - 1);
    }

    private void quickSortBaseFirst(int[] ary, int left, int right) {
        if (left >= right)
            return;
        int temp = ary[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (ary[j] >= temp && i < j) {
                j--;
            }
            while (ary[i] <= temp && i < j) {
                i++;
            }
            if (i < j) {
                int t = ary[i];
                ary[i] = ary[j];
                ary[j] = t;
            }
        }
        // 把基准元素放回到该放的位置
        ary[left] = ary[i];
        ary[i] = temp;
        quickSortBaseFirst(ary, left, i - 1);
        quickSortBaseFirst(ary, i +1 , right);

    }


    // 中间数做基数
    private void quickSortBaseMiddle(int[] ary, int left, int right) {
        // 基数的话，本质上还是需要挪到最左边或者最右边
    }
}
